COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00006 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn on "∂→"
CS206 ∂(20)COMPUTING WITH SYMBOLIC EXPRESSIONS →FALL 1976
.SKIP 2
.ONCE CENTER
MIDTERM
.skip 1
.once center
(Open books and notes)

	Write LISP functions as follows using either external or internal
notation according to your preference.

1.∂5(a) %2element1[u,n]%1 is the %2n%1th element of the list %2u%1 and
%1ERROR%1 if there is no such element.

	(b) %2element2[x,s]%1 is the subexpression at position %2s%1 in
the S-expression %2x%1, where %2s%1 is a list of whose elements are %1A%1
or %1D%1 and the position is determined by taking %3a%* and %3d%* according to
the elements of %2s%1.  Thus %2element2[%1(PLUS (TIMES X Y) X), (D A D D)%1] =
%1(Y)%1.  The value of the function is %1ERROR%1 if there is no such element.

2.∂5(a) %2selectatoms1 u%1 is a list of the atoms of the list %2u%1.

	(b) %2selectatoms2 x%1 is a list without repetitions of the atoms
of the S-expression %2x%1.

	(c) %2select1[p,u]%1 is a list of the elements of the list %2u%1
that satisfy the predicate %2p%1.

	(d) %2select2[p,x]%1 is a list of the subexpressions of the
S-expression %2x%1 that satisfy the predicate %2p%1.

	(e) %2select3[p,x]%1 is a list of the positions of the subexpressions
of the S-expression %2x%1 that satisfy the predicate %2p%1.
Use the notation for positions described in problem 1.

3. Suppose %2successors x%1 gives a list of the successor nodes of
the node %2x%1 in some graph.

	(a) %2find[x,p]%1 is a node satisfying the predicate %2p%1.

	(b) %2findall[x,p]%1 is a list of all nodes satisfying the
predicate %2p%1.

4. A "program" in the language %2L%1 is a list of statements and labels
where a label is an atom.  Each statement has one of three forms
(GO <label>), (IF <anything> <label>) or <a list not beginning with IF or GO>.
A "program" π satisfies the predicate %2ok[π]%1 if no label occurs more
than once and every label occurring in a GO or IF statement occurs in the
program.  Write the predicate %2ok[π]%1.